<template>
    <ExamPaper :items="paper" :name="title" @update:answers="val => (finalAnswers = val)" />
</template>

<script setup>
import { ref, onMounted, computed } from 'vue'
import ExamPaper from '@/components/ExamPaper.vue'
// 使用路由meta中的name作为标题
import { useRoute } from 'vue-router'
const route = useRoute()
const title = computed(() => {
    return route.meta.title || '算法题库'
})

const paper = ref([
    {
        question: `
        请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
        实现 LRUCache 类：
        LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
        int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
        void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存
        中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键
        字。
        函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
        示例：
        输入
        ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
        [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
        输出
        [null, null, null, 1, null, -1, null, -1, 3, 4]
        解释
        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(1, 1); // 缓存是 {1=1}
        lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
        lRUCache.get(1);  // 返回 1
        lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        lRUCache.get(2);  // 返回 -1 (未找到)
        lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
        lRUCache.get(1);  // 返回 -1 (未找到)
        lRUCache.get(3);  // 返回 3
        lRUCache.get(4);  // 返回 4
        `,
        answer: `
        class LRUCache {
            constructor(cacheLength) {
                this.maxSize = cacheLength;
                this.map = new Map();
            }
            get(key){
                const value = this.map.get(key)||-1
                if(value!= -1){
                    this.map.delete(key)
                    this.map.set(key,value)
                }
                return value
            }
            put(key,value){
                if(this.map.has(key)){
                this.map.delete(key)
                this.map.set(key,value)
                }else{
                if(this.map.size == this.maxSize){
                    this.map = new Map(Array.from(this.map).slice(1))
                }
                this.map.set(key,value)
                }
            }
        }
        `,
        remark: `
        有点难，如果没有Map数据结构的话，自己实现一个双向链表和哈希表结合的结构我是没有思路的。
        有请AI来帮我用双向链表和哈希表结合的结构实现一下
        // 双向链表节点
        function DLinkNode(key, val) {
            this.key = key;
            this.val = val;
            this.prev = null;
            this.next = null;
        }

        // LRU 缓存构造器
        function LRUCache(capacity) {
            this.cap = capacity;
            this.size = 0;
            this.hash = {};          // key -> DLinkNode
            this.head = new DLinkNode(); // 伪头
            this.tail = new DLinkNode(); // 伪尾
            this.head.next = this.tail;
            this.tail.prev = this.head;
        }

        // 私有工具：把节点插到伪头之后（最新位置）
        LRUCache.prototype._addNode = function (node) {
            node.prev = this.head;
            node.next = this.head.next;
            this.head.next.prev = node;
            this.head.next = node;
        };

        // 私有工具：删除指定节点
        LRUCache.prototype._removeNode = function (node) {
            var prev = node.prev,
                next = node.next;
            prev.next = next;
            next.prev = prev;
        };

        // 私有工具：把节点移到头部（表示刚用过）
        LRUCache.prototype._moveToHead = function (node) {
            this._removeNode(node);
            this._addNode(node);
        };

        // 私有工具：淘汰尾部最久未使用节点
        LRUCache.prototype._popTail = function () {
            var last = this.tail.prev;
            this._removeNode(last);
            return last;
        };

        // 查询
        LRUCache.prototype.get = function (key) {
            var node = this.hash[key];
            if (!node) return -1;
            this._moveToHead(node);
            return node.val;
        };

        // 插入/更新
        LRUCache.prototype.put = function (key, value) {
            var node = this.hash[key];

            if (node) {               // 已存在，更新值并移到头部
                node.val = value;
                this._moveToHead(node);
                return;
            }

            // 新增
            node = new DLinkNode(key, value);
            this.hash[key] = node;
            this._addNode(node);
            this.size++;

            if (this.size > this.cap) {   // 超限，淘汰尾部
                var tail = this._popTail();
                delete this.hash[tail.key];
                this.size--;
            }
        };

        // ------------------ 测试 ------------------
        var cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        console.log(cache.get(1)); // 1
        cache.put(3, 3);           // 淘汰 2
        console.log(cache.get(2)); // -1
        cache.put(4, 4);           // 淘汰 1
        console.log(cache.get(1)); // -1
        console.log(cache.get(3)); // 3
        console.log(cache.get(4)); // 4

        `
    }, {
        question: `
        你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素
        就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报
        警。
        给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃
        到的最高金额。
        示例 1：
        1
        2
        3
        4
        输入：[1,2,3,1]
        输出：4
        解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
        偷窃到的最高金额 = 1 + 3 = 4 。
        示例 2：
        1
        2
        3
        4
        输入：[2,7,9,3,1]
        输出：12
        解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 
        1)。
        偷窃到的最高金额 = 2 + 9 + 1 = 12 。
        提示：
        1 <= nums.length <= 100
        0 <= nums[i] <= 400
        `,
        answer: `
        function deal2(nums){
            let maxNum = 0;
            function step(index,numTotal){
                if(numTotal>maxNum){
                maxNum = numTotal
                }
                if(index>=nums.length){
                return
                }
                for(let i = index+2;i<nums.length; i++){
                step(i,numTotal+nums[i])
                }
            }
            nums.forEach((num,index)=>{
                step(index,num)
            })
            return maxNum
        }

        优化下写成这样不可能连续两个不取所以优化下循环

        function deal2(nums){
            let maxNum = 0;
            function step(index,numTotal){
                if(numTotal>maxNum){
                maxNum = numTotal
                }
                if(index>=nums.length){
                return
                }
                for(let i = index+2;i<nums.length && i<index+4; i++){
                step(i,numTotal+nums[i])
                }
            }
            nums.forEach((num,index)=>{
                if(index<2){
                    step(index,num)
                } 
            })

            return maxNum
        }
        //虽然加了限制时间复杂度仍然为O(2^n)
        `,
        remark: `
        这个题目用递归暴力破解是可以的，但是时间复杂度太高了，O(2^n)，面试肯定不行。
        这个题目是典型的动态规划问题，动态规划的核心是找到状态转移方程。
        设 dp[i] 为偷窃到第 i 间房屋时的最高金额，则状态转移方程为：
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
        解释：
        如果不偷第 i 间房屋，那么 dp[i] = dp[i-1]。
        如果偷第 i 间房屋，那么 dp[i] = dp[i-2] + nums[i]。
        于是可以得到动态规划的状态转移方程为：
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
        其中 dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])。
        于是可以得到动态规划的状态转移方程为：
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
        其中 dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])。
        于是可以得到动态规划的状态转移方程为：
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
        其中 dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])。
        代码实现如下：
        function rob(nums) {
            if (nums.length === 0) return 0;
            if (nums.length === 1) return nums[0];
            const dp = new Array(nums.length);
            dp[0] = nums[0];
            dp[1] = Math.max(nums[0], nums[1]);
            for (let i = 2; i < nums.length; i++) {
                dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
            }
            return dp[nums.length - 1];
        }
        时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们只需要遍历一次数组即可得到结果。
        空间复杂度：O(n)，我们使用了一个长度为 n 的数组 dp 来存储中间结果。
        其实我们可以优化空间复杂度，因为 dp[i] 只依赖于 dp[i-1] 和 dp[i-2]，所以我们只需要两个变量来存储这两个值即可。
        优化后的代码实现如下：
        function rob(nums) {
            if (nums.length === 0) return 0;
            if (nums.length === 1) return nums[0];
            let prev1 = Math.max(nums[0], nums[1]);
            let prev2 = nums[0];
            for (let i = 2; i < nums.length; i++) {
                const curr = Math.max(prev1, prev2 + nums[i]);
                prev2 = prev1;
                prev1 = curr;
            }
            return prev1;
        }
        时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们只需要遍历一次数组即可得到结果。
        空间复杂度：O(1)，我们只使用了常数个变量来存储中间结果。


        负数对“偷钱”问题其实毫无影响——因为“不偷”对应的收益是 0，而金额数组里出现负数时，最优策略直接跳过该房屋即可。
        因此完全不需要改状态转移方程，只要把“不偷”的基准收益保持为 0，算法仍然成立。
        下面给出可直接处理负数的两种写法（与正数版代码一字不改）：
        JavaScript
        复制
        /**
         * @param {number[]} nums  允许存在负数
         * @return {number}
         */

        /* 1. 标准 dp 数组版 */
        var rob = function (nums) {
            const n = nums.length;
            if (n === 0) return 0;
            if (n === 1) return Math.max(0, nums[0]);   // 防一手全是负数

            const dp = new Array(n);
            dp[0] = Math.max(0, nums[0]);
            dp[1] = Math.max(dp[0], nums[1]);

            for (let i = 2; i < n; i++) {
                dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);
            }
            return dp[n - 1];
        };

        /* 2. O(1) 空间压缩版 */
        var rob = function (nums) {
            let prev2 = 0;   // dp[i-2]
            let prev1 = 0;   // dp[i-1]

            for (const num of nums) {
                const cur = Math.max(num + prev2, prev1);
                prev2 = prev1;
                prev1 = cur;
            }
            return prev1;
        };
        `
    }, {
        question: `
        给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
        树的 最大宽度 是所有层中最大的 宽度 。
        每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与
        满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
        题目数据保证答案将会在 32 位 带符号整数范围内。
        示例 1：
        <img src="">
        输入：root = [1,3,2,5,3,null,9]
        输出：4
        解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 

        示例 2：
        <img src="">
        输入：root = [1,3,2,5,null,null,9,6,null,7]
        输出：7
        解释：最大宽度出现在树的第 4 层，宽度为 7 (6,null,null,null,null,null,7) 

        示例 3：
        <img src="">
        输入：root = [1,3,2,5]
        输出：2
        解释：最大宽度出现在树的第 2 层，宽度为 2 (3,2)
        `,
        answer: `
        function deal3(root) {
            const deepsLength = [];
            function step(node, deep, nodeIndex) {
                console.log(node.val,nodeIndex)
                if (node == null) {
                    return
                }
                if (!deepsLength[deep]) {
                    deepsLength[deep] = {
                        min: nodeIndex,
                        max: nodeIndex
                    }
                } else {
                    if (nodeIndex < deepsLength[deep].min) {
                        deepsLength[deep].min = nodeIndex
                    }
                    if (nodeIndex > deepsLength[deep].max) {
                        deepsLength[deep].max = nodeIndex
                    }
                }
                if (node.left) {
                    step(node.left, deep + 1, 2 * nodeIndex -1)
                }
                if (node.right) {
                    step(node.right, deep + 1, 2 * nodeIndex)
                }
            };
            step(root, 0, 1)
            deepsLength.sort((a, b) => {
                return (a.max - a.min) > (b.max - b.min) ? -1 : 1
            })
            
            return deepsLength[0].max - deepsLength[0].min + 1
        }
        `,
        remark: `
        `
    }
])

onMounted(() => {
    // 用例2
    const root = {
        val: 1,
        left: {
            val: 3,
            left: {
                val: 5,
                left: {
                    val: 6
                },
                right: null
            },
            right: null
        },
        right: {
            val: 2,
            left: null,
            right: {
                val: 9,
                left: {
                    val: 7
                },
                right: null
            }
        }
    }
})


const finalAnswers = ref([])   // 实时收集到的答案
</script>